home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 2 / AACD 2.iso / AACD / Programming / jikes-1.02 / src / lookup.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1999-09-01  |  46.9 KB  |  1,741 lines
  1. // $Id: lookup.cpp,v 1.13 1999/09/01 14:58:25 shields Exp $
  2. //
  3. // This software is subject to the terms of the IBM Jikes Compiler
  4. // License Agreement available at the following URL:
  5. // http://www.ibm.com/research/jikes.
  6. // Copyright (C) 1996, 1998, International Business Machines Corporation
  7. // and others.  All Rights Reserved.
  8. // You must accept the terms of that agreement to use this software.
  9. //
  10. #include "config.h"
  11. #include <iostream.h>
  12. #include "lookup.h"
  13. #include "symbol.h"
  14. #include "code.h"
  15. #include "ast.h"
  16. #include "case.h"
  17.  
  18. int SystemTable::primes[] = {DEFAULT_HASH_SIZE, 101, 401, MAX_HASH_SIZE};
  19.  
  20. SystemTable::SystemTable(int hash_size_) : directories(1024)
  21. {
  22.     hash_size = (hash_size_ <= 0 ? 1 : hash_size_);
  23.  
  24.     prime_index = -1;
  25.     do
  26.     {
  27.         if (hash_size < primes[prime_index + 1])
  28.             break;
  29.         prime_index++;
  30.     } while (primes[prime_index] < MAX_HASH_SIZE);
  31.  
  32.     base = (Element **) memset(new Element *[hash_size], 0, hash_size * sizeof(Element *));
  33. }
  34.  
  35. SystemTable::~SystemTable()
  36. {
  37.     for (int i = 0; i < directories.Length(); i++)
  38.         delete directories[i];
  39. }
  40.  
  41. void SystemTable::Rehash()
  42. {
  43.     hash_size = primes[++prime_index];
  44.  
  45.     delete [] base;
  46.     base = (Element **) memset(new Element *[hash_size], 0, hash_size * sizeof(Element *));
  47.  
  48.     for (int k = 0; k < directories.Length(); k++)
  49.     {
  50.         Element *element = directories[k];
  51.  
  52.         int i = hash(element -> device, element -> inode);
  53.         element -> next = base[i];
  54.         base[i] = element;
  55.     }
  56.  
  57.     return;
  58. }
  59.  
  60. DirectorySymbol *SystemTable::FindDirectorySymbol(dev_t device, ino_t inode)
  61. {
  62.     int k = hash(device, inode);
  63.  
  64.     for (Element *element = base[k]; element; element = element -> next)
  65.     {
  66.         if (element -> device == device && element -> inode == inode)
  67.             return element -> directory_symbol;
  68.     }
  69.  
  70.     return NULL;
  71. }
  72.  
  73. void SystemTable::InsertDirectorySymbol(dev_t device, ino_t inode, DirectorySymbol *directory_symbol)
  74. {
  75.     int k = hash(device, inode);
  76.  
  77.     Element *element = new Element(device, inode, directory_symbol);
  78.     directories.Next() = element;
  79.  
  80.     element -> next = base[k];
  81.     base[k] = element;
  82.  
  83.     //
  84.     // If the set is "adjustable" and the number of unique elements in it exceeds
  85.     // 2 times the size of the base, and we have not yet reached the maximum
  86.     // allowable size for a base, reallocate a larger base and rehash the elements.
  87.     //
  88.     if ((directories.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  89.         Rehash();
  90.  
  91.     return;
  92. }
  93.  
  94. int DirectoryTable::primes[] = {DEFAULT_HASH_SIZE, 2039, 4093, MAX_HASH_SIZE};
  95.  
  96. DirectoryTable::DirectoryTable(int estimate) : entry_pool(estimate),
  97.                                                prime_index(0),
  98.                                                hash_size(primes[0])
  99. {
  100.     base = (DirectoryEntry **) memset(new DirectoryEntry *[hash_size], 0, hash_size * sizeof(DirectoryEntry *));
  101. }
  102.  
  103. DirectoryTable::~DirectoryTable()
  104. {
  105. /*
  106. int n;
  107. int num_slots = 0;
  108. int total = 0;
  109. for (n = 0; n < hash_size; n++)
  110. {
  111. int num = 0;
  112. for (Symbol *s = base[n]; s; s = s -> next)
  113.     num++;
  114. if (num > 0)
  115. {
  116. num_slots++;
  117. total += num;
  118. }
  119. }
  120.  
  121. if (num_slots > 0)
  122. {
  123. Coutput << "\nDestroying the Name table with " << total
  124.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  125. for (n = 0; n < hash_size; n++)
  126. {
  127. int num = 0;
  128. for (Symbol *s = base[n]; s; s = s -> next)
  129.     num++;
  130. if (num > 0)
  131. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  132. }
  133. }
  134. if (hash_size < total)
  135.     total = total;
  136. */
  137. #ifdef TEST
  138.     for (int i = 0; i < entry_pool.Length(); i++)
  139.         delete entry_pool[i];
  140.     delete [] base;
  141. #endif
  142. }
  143.  
  144.  
  145. DirectoryEntry *DirectoryTable::FindEntry(char *str, int len)
  146. {
  147.     int k = Hash(str, len) % hash_size;
  148.     DirectoryEntry *entry;
  149.     for (entry = base[k]; entry; entry = entry -> next)
  150.     {
  151.         if (len == entry -> length && memcmp(entry -> name, str, len * sizeof(char)) == 0)
  152.             return (entry -> IsDummy() ? (DirectoryEntry *) NULL : entry);
  153.     }
  154.  
  155.     return NULL;
  156. }
  157.  
  158.  
  159. void DirectoryTable::Rehash()
  160. {
  161.     hash_size = primes[++prime_index];
  162.  
  163.     delete [] base;
  164.     base = (DirectoryEntry **) memset(new DirectoryEntry *[hash_size], 0, hash_size * sizeof(DirectoryEntry *));
  165.  
  166.     for (int i = 0; i < entry_pool.Length(); i++)
  167.     {
  168.         DirectoryEntry *e = entry_pool[i];
  169.         int k = Hash(e -> name, e -> length) % hash_size;
  170.         e -> next = base[k];
  171.         base[k] = e;
  172.     }
  173.  
  174.     return;
  175. }
  176.  
  177.  
  178. DirectoryEntry *DirectoryTable::InsertEntry(DirectorySymbol *directory_symbol, char *str, int len)
  179. {
  180.     int k = Hash(str, len) % hash_size;
  181.     DirectoryEntry *entry;
  182.     for (entry = base[k]; entry; entry = entry -> next)
  183.     {
  184.         if (len == entry -> length && memcmp(entry -> name, str, len * sizeof(char)) == 0)
  185.             return entry;
  186.     }
  187.  
  188.     entry = new DirectoryEntry();
  189.     entry_pool.Next() = entry;
  190.     entry -> Initialize(directory_symbol, str, len);
  191.  
  192.     entry -> next = base[k];
  193.     base[k] = entry;
  194.  
  195.     //
  196.     // If the number of unique elements in the hash table exceeds 2 times
  197.     // the size of the base, and we have not yet reached the maximum
  198.     // allowable size for a base, reallocate a larger base and rehash
  199.     // the elements.
  200.     //
  201.     if ((entry_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  202.         Rehash();
  203.  
  204.     return entry;
  205. }
  206.  
  207.  
  208. #ifdef WIN32_FILE_SYSTEM
  209. DirectoryEntry *DirectoryTable::FindCaseInsensitiveEntry(char *name, int length)
  210. {
  211.     char *lower_name = new char[length + 1];
  212.     for (int i = 0; i < length; i++)
  213.         lower_name[i] = Case::ToAsciiLower(name[i]);
  214.     lower_name[length] = U_NULL;
  215.  
  216.     DirectoryEntry *entry = FindEntry(lower_name, length);
  217.     delete [] lower_name;
  218.  
  219.     return (entry ? entry -> Image() : entry);
  220. }
  221.  
  222. void DirectoryTable::InsertCaseInsensitiveEntry(DirectoryEntry *image)
  223. {
  224.     int length = image -> length;
  225.     char *lower_name = new char[length + 1];
  226.     for (int i = 0; i < length; i++)
  227.         lower_name[i] = Case::ToAsciiLower(image -> name[i]);
  228.     lower_name[length] = U_NULL;
  229.  
  230.     int k = Hash(lower_name, length) % hash_size;
  231.     DirectoryEntry *entry;
  232.     for (entry = base[k]; entry; entry = entry -> next)
  233.     {
  234.         if (length == entry -> length && memcmp(entry -> name, lower_name, length * sizeof(char)) == 0)
  235.             break;
  236.     }
  237.  
  238.     if (! entry)
  239.     {
  240.         FoldedDirectoryEntry *folded_entry = new FoldedDirectoryEntry(image);
  241.         entry_pool.Next() = folded_entry;
  242.         folded_entry -> Initialize(image, lower_name, length);
  243.  
  244.         folded_entry -> next = base[k];
  245.         base[k] = folded_entry;
  246.  
  247.         //
  248.         // If the number of unique elements in the hash table exceeds 2 times
  249.         // the size of the base, and we have not yet reached the maximum
  250.         // allowable size for a base, reallocate a larger base and rehash
  251.         // the elements.
  252.         //
  253.         if ((entry_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  254.             Rehash();
  255.     }
  256.  
  257.     delete [] lower_name;
  258.  
  259.     return;
  260. }
  261. #endif
  262.  
  263.  
  264. time_t DirectoryEntry::Mtime()
  265. {
  266.     if (mtime_ == 0)
  267.     {
  268.         char *dirname = this -> directory -> DirectoryName();
  269.         int length = this -> directory -> DirectoryNameLength() + this -> length + 1; // +1 for '/'
  270.         char *file_name = new char[length + 1];
  271.         strcpy(file_name, dirname);
  272.         if (dirname[this -> directory -> DirectoryNameLength() - 1] != U_SLASH)
  273.             strcat(file_name, StringConstant::U8S__SL);
  274.         strcat(file_name, this -> name);
  275.  
  276.         struct stat status;
  277.         if (::SystemStat(file_name, &status) == 0)
  278.              mtime_ = status.st_mtime;
  279.         else assert(false && "Cannot compute system time stamp\n");
  280.  
  281.         delete [] file_name;
  282.     }
  283.  
  284.     return mtime_;
  285. }
  286.  
  287.  
  288. int NameLookupTable::primes[] = {DEFAULT_HASH_SIZE, 8191, 16411, MAX_HASH_SIZE};
  289.  
  290. NameLookupTable::NameLookupTable(int estimate) : symbol_pool(estimate),
  291.                                                  prime_index(0),
  292.                                                  hash_size(primes[0])
  293. {
  294.     base = (NameSymbol **) memset(new NameSymbol *[hash_size], 0, hash_size * sizeof(NameSymbol *));
  295. }
  296.  
  297. NameLookupTable::~NameLookupTable()
  298. {
  299. /*
  300. int n;
  301. int num_slots = 0;
  302. int total = 0;
  303. for (n = 0; n < hash_size; n++)
  304. {
  305. int num = 0;
  306. for (Symbol *s = base[n]; s; s = s -> next)
  307.     num++;
  308. if (num > 0)
  309. {
  310. num_slots++;
  311. total += num;
  312. }
  313. }
  314.  
  315. if (num_slots > 0)
  316. {
  317. Coutput << "\nDestroying the Name table with " << total
  318.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  319. for (n = 0; n < hash_size; n++)
  320. {
  321. int num = 0;
  322. for (Symbol *s = base[n]; s; s = s -> next)
  323.     num++;
  324. if (num > 0)
  325. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  326. }
  327. }
  328. if (hash_size < total)
  329.     total = total;
  330. */
  331. #ifdef TEST
  332.     for (int i = 0; i < symbol_pool.Length(); i++)
  333.         delete symbol_pool[i];
  334.     delete [] base;
  335. #endif
  336. }
  337.  
  338.  
  339. void NameLookupTable::Rehash()
  340. {
  341.     hash_size = primes[++prime_index];
  342.  
  343.     delete [] base;
  344.     base = (NameSymbol **) memset(new NameSymbol *[hash_size], 0, hash_size * sizeof(NameSymbol *));
  345.  
  346.     for (int i = 0; i < symbol_pool.Length(); i++)
  347.     {
  348.         NameSymbol *ns = symbol_pool[i];
  349.         int k = ns -> hash_address % hash_size;
  350.         ns -> next = base[k];
  351.         base[k] = ns;
  352.     }
  353.  
  354.     return;
  355. }
  356.  
  357.  
  358. NameSymbol *NameLookupTable::FindOrInsertName(wchar_t *str, int len)
  359. {
  360.     unsigned hash_address = Hash(str, len);
  361.     int k = hash_address % hash_size;
  362.     NameSymbol *symbol;
  363.     for (symbol = base[k]; symbol; symbol = (NameSymbol *) symbol -> next)
  364.     {
  365.         if (len == symbol -> NameLength() && memcmp(symbol -> Name(), str, len * sizeof(wchar_t)) == 0)
  366.             return symbol;
  367.     }
  368.  
  369.     int index = symbol_pool.Length(); // index of the next element
  370.     symbol = new NameSymbol();
  371.     symbol_pool.Next() = symbol;
  372.     symbol -> Initialize(str, len, hash_address, index);
  373.  
  374.     symbol -> next = base[k];
  375.     base[k] = symbol;
  376.  
  377.     //
  378.     // If the number of unique elements in the hash table exceeds 2 times
  379.     // the size of the base, and we have not yet reached the maximum
  380.     // allowable size for a base, reallocate a larger base and rehash
  381.     // the elements.
  382.     //
  383.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  384.         Rehash();
  385.  
  386.     return symbol;
  387. }
  388.  
  389.  
  390. int TypeLookupTable::primes[] = {DEFAULT_HASH_SIZE, 8191, 16411, MAX_HASH_SIZE};
  391.  
  392. TypeLookupTable::TypeLookupTable(int estimate) : symbol_pool(estimate),
  393.                                                  prime_index(0),
  394.                                                  hash_size(primes[0])
  395. {
  396.     base = (TypeSymbol **) memset(new TypeSymbol *[hash_size], 0, hash_size * sizeof(TypeSymbol *));
  397. }
  398.  
  399. TypeLookupTable::~TypeLookupTable()
  400. {
  401. /*
  402. int n;
  403. int num_slots = 0;
  404. int total = 0;
  405. for (n = 0; n < hash_size; n++)
  406. {
  407. int num = 0;
  408. for (TypeSymbol *s = base[n]; s; s = s -> next_type)
  409.     num++;
  410. if (num > 0)
  411. {
  412. num_slots++;
  413. total += num;
  414. }
  415. }
  416.  
  417. if (num_slots > 0)
  418. {
  419. Coutput << "\nDestroying the Type table with " << total
  420.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  421. for (n = 0; n < hash_size; n++)
  422. {
  423. int num = 0;
  424. for (TypeSymbol *s = base[n]; s; s = s -> next_type)
  425.     num++;
  426. if (num > 0)
  427. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  428. }
  429. }
  430. if (hash_size < total)
  431.     total = total;
  432. */
  433. }
  434.  
  435.  
  436. void TypeLookupTable::Rehash()
  437. {
  438.     hash_size = primes[++prime_index];
  439.  
  440.     delete [] base;
  441.     base = (TypeSymbol **) memset(new TypeSymbol *[hash_size], 0, hash_size * sizeof(TypeSymbol *));
  442.  
  443.     for (int i = 0; i < symbol_pool.Length(); i++)
  444.     {
  445.         TypeSymbol *type = symbol_pool[i];
  446.         int k = type -> hash_address % hash_size;
  447.         type -> next_type = base[k];
  448.         base[k] = type;
  449.     }
  450.  
  451.     return;
  452. }
  453.  
  454.  
  455. TypeSymbol *TypeLookupTable::FindType(char *str, int len)
  456. {
  457.     unsigned hash_address = Hash(str, len);
  458.     int k = hash_address % hash_size;
  459.     for (TypeSymbol *type = base[k]; type; type = type -> next_type)
  460.     {
  461.         Utf8LiteralValue *fully_qualified_name = type -> fully_qualified_name;
  462.         if (len == fully_qualified_name -> length && memcmp(fully_qualified_name -> value, str, len * sizeof(char)) == 0)
  463.             return type;
  464.     }
  465.  
  466.     return NULL;
  467. }
  468.  
  469.  
  470. void TypeLookupTable::InsertType(TypeSymbol *type)
  471. {
  472.     unsigned hash_address = Hash(type -> fully_qualified_name -> value, type -> fully_qualified_name -> length);
  473.     int k = hash_address % hash_size;
  474.  
  475. #ifdef TEST
  476.     for (TypeSymbol *t = base[k]; t; t = t -> next_type)
  477.         assert (type != t && "Type was already entered in type table");
  478. #endif
  479.  
  480.     symbol_pool.Next() = type;
  481.     type -> hash_address = hash_address;
  482.  
  483.     type -> next_type = base[k];
  484.     base[k] = type;
  485.  
  486.     //
  487.     // If the number of unique elements in the hash table exceeds 2 times
  488.     // the size of the base, and we have not yet reached the maximum
  489.     // allowable size for a base, reallocate a larger base and rehash
  490.     // the elements.
  491.     //
  492.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  493.         Rehash();
  494.  
  495.     return;
  496. }
  497.  
  498.  
  499. int IntLiteralTable::int32_limit = 0x7FFFFFFF / 10;
  500. int IntLiteralTable::primes[] = {DEFAULT_HASH_SIZE, 8191, 16411, MAX_HASH_SIZE};
  501.  
  502. IntLiteralTable::IntLiteralTable(LiteralValue *bad_value_) : symbol_pool(16384),
  503.                                                              bad_value(bad_value_),
  504.                                                              prime_index(0),
  505.                                                              hash_size(primes[0])
  506. {
  507.     base = (IntLiteralValue **) memset(new IntLiteralValue *[hash_size], 0, hash_size * sizeof(IntLiteralValue *));
  508.     symbol_pool.Next() = NULL; // do not use the 0th element
  509. }
  510.  
  511. IntLiteralTable::~IntLiteralTable()
  512. {
  513. /*
  514. int n;
  515. int num_slots = 0;
  516. int total = 0;
  517. for (n = 0; n < hash_size; n++)
  518. {
  519. int num = 0;
  520. for (LiteralValue *s = base[n]; s; s = s -> next)
  521.     num++;
  522. if (num > 0)
  523. {
  524. num_slots++;
  525. total += num;
  526. }
  527. }
  528.  
  529. if (num_slots > 0)
  530. {
  531. Coutput << "\nDestroying the integer table with " << total
  532.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  533. for (n = 0; n < hash_size; n++)
  534. {
  535. int num = 0;
  536. for (LiteralValue *s = base[n]; s; s = s -> next)
  537.     num++;
  538. if (num > 0)
  539. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  540. }
  541. }
  542. if (hash_size < total)
  543.     total = total;
  544. */
  545.  
  546. #ifdef TEST
  547.     for (int i = 0; i < symbol_pool.Length(); i++)
  548.         delete symbol_pool[i];
  549.     delete [] base;
  550. #endif
  551. }
  552.  
  553.  
  554. LiteralValue *IntLiteralTable::FindOrInsertChar(LiteralSymbol *literal)
  555. {
  556.     wchar_t *name = literal -> Name();
  557.  
  558.     if (literal -> NameLength() == 1) // an isolated quote
  559.          return literal -> value = bad_value;
  560.     else if (literal -> NameLength() <= 3) // a regular character of the form:  quote + char
  561.                                            // or                                quote + char + quote
  562.          return literal -> value = FindOrInsert((int) name[1]);
  563.  
  564.     int value;
  565.  
  566.     if (name[1] != U_BACKSLASH)
  567.          value = -1;
  568.     else if (name[2] == U_b && name[3] == U_SINGLE_QUOTE)
  569.          value = U_BACKSPACE;
  570.     else if (name[2] == U_t && name[3] == U_SINGLE_QUOTE)
  571.          value = U_HORIZONTAL_TAB;
  572.     else if (name[2] == U_n && name[3] == U_SINGLE_QUOTE)
  573.          value = U_LINE_FEED;
  574.     else if (name[2] == U_f && name[3] == U_SINGLE_QUOTE)
  575.          value = U_FORM_FEED;
  576.     else if (name[2] == U_r && name[3] == U_SINGLE_QUOTE)
  577.          value = U_CARRIAGE_RETURN;
  578.     else if (name[2] == U_DOUBLE_QUOTE && name[3] == U_SINGLE_QUOTE)
  579.          value = U_DOUBLE_QUOTE;
  580.     else if (name[2] == U_SINGLE_QUOTE && name[3] == U_SINGLE_QUOTE)
  581.          value = U_SINGLE_QUOTE;
  582.     else if (name[2] == U_BACKSLASH && name[3] == U_SINGLE_QUOTE)
  583.          value = U_BACKSLASH;
  584.     else if (Code::IsDigit(name[2]))
  585.     {
  586.         wchar_t *p = &name[2];
  587.  
  588.         int d1 = *p++ - U_0;
  589.         value = (d1 < 8 ? d1 : -1);
  590.  
  591.         if (value >= 0 && Code::IsDigit(*p))
  592.         {
  593.             int d2 = *p++ - U_0;
  594.             value = (d2 < 8 ? value * 8 + d2 : -1);
  595.  
  596.             if (value >= 0 && Code::IsDigit(*p))
  597.             {
  598.                 int d3 = *p++ - U_0;
  599.                 value = (d3 < 8 && d1 < 4 ? value * 8 + d3 : -1);
  600.             }
  601.         }
  602.  
  603.         if (*p != U_NULL && *p != U_SINGLE_QUOTE)
  604.             value = -1;
  605.     }
  606.     else value = -1;
  607.  
  608.     return literal -> value = (value < 0 || value > 65535 ? bad_value : FindOrInsert(value));
  609. }
  610.  
  611.  
  612. LiteralValue *IntLiteralTable::FindOrInsertHexInt(LiteralSymbol *literal)
  613. {
  614.     wchar_t *head = literal -> Name() + 1, // point to X
  615.             *tail = &literal -> Name()[literal -> NameLength() - 1];
  616.  
  617.     u4 uvalue = 0;
  618.  
  619.     //
  620.     // According to the JLS 3.10.1, "A compile-time error occurs if ... a
  621.     // hexadecimal or octal int literal does not fit in 32 bits".
  622.     // So, strictly speaking, we should not skip leading zeroes. However,
  623.     // there are many publicly available code out there with leading zeroes
  624.     // that don't compile with jikes, if ...
  625.     //
  626.     {
  627.         for (++head; tail > head && *head == U_0; head++) // skip leading zeroes
  628.             ;
  629.         head--;
  630.     }
  631.  
  632.     for (int i = 0; i < 32 && tail > head; i += 4, tail--)
  633.     {
  634.         u4 d = *tail - (Code::IsDigit(*tail) ? U_0 : (Code::IsLower(*tail) ? U_a : U_A) - 10);
  635.         uvalue |= (d << i);
  636.     }
  637.  
  638.     return (tail > head ? bad_value : FindOrInsert((int) uvalue));
  639. }
  640.  
  641.  
  642. LiteralValue *IntLiteralTable::FindOrInsertOctalInt(LiteralSymbol *literal)
  643. {
  644.     wchar_t *head = literal -> Name(), // point to initial '0'
  645.             *tail = &head[literal -> NameLength() - 1];
  646.  
  647.     u4 uvalue = 0;
  648.     //
  649.     // According to the JLS 3.10.1, "A compile-time error occurs if ... a
  650.     // hexadecimal or octal int literal does not fit in 32 bits".
  651.     // So, strictly speaking, we should not skip leading zeroes. However,
  652.     // there are many publicly available code out there with leading zeroes
  653.     // that don't compile with jikes,...
  654.     //
  655.     {
  656.         for (++head; tail > head && *head == U_0; head++) // skip leading zeroes
  657.             ;
  658.         head--;
  659.     }
  660.  
  661.     for (int i = 0; i < 30 && tail > head; i += 3, tail--)
  662.     {
  663.         u4 d = *tail - U_0;
  664.         uvalue |= (d << i);
  665.     }
  666.  
  667.     if (tail > head)
  668.     {
  669.         u4 d = *tail - U_0;
  670.  
  671.         if (d <= 3) // max number that can fit in 2 bits
  672.         {
  673.             tail--;
  674.             uvalue |= (d << 30);
  675.         }
  676.     }
  677.  
  678.     return (tail > head ? bad_value : FindOrInsert((int) uvalue));
  679. }
  680.  
  681.  
  682. LiteralValue *IntLiteralTable::FindOrInsertInt(LiteralSymbol *literal)
  683. {
  684.     wchar_t *name = literal -> Name();
  685.  
  686.     if (name[0] == U_0)
  687.         literal -> value = (name[1] == U_x || name[1] == U_X ? FindOrInsertHexInt(literal) : FindOrInsertOctalInt(literal));
  688.     else
  689.     {
  690.         int value = 0;
  691.  
  692.         wchar_t *p;
  693.         for (p = name; *p; p++)
  694.         {
  695.             int digit = *p - U_0;
  696.             if (value > int32_limit || (value == int32_limit && digit > 7))
  697.                 break;
  698.             value = value * 10 + digit;
  699.         }
  700.  
  701.         literal -> value = (*p ? bad_value : FindOrInsert(value));
  702.     }
  703.  
  704.     return literal -> value;
  705. }
  706.  
  707.  
  708. LiteralValue *IntLiteralTable::FindOrInsertNegativeInt(LiteralSymbol *literal)
  709. {
  710.     if (literal -> value && literal -> value != bad_value) // a positive value already exists
  711.     {
  712.         IntLiteralValue *int_literal = (IntLiteralValue *) literal -> value;
  713.         return FindOrInsert(- int_literal -> value);
  714.     }
  715.  
  716.     wchar_t *name = literal -> Name();
  717.  
  718.     //
  719.     // We can assert that the name of a literal contains at least two characters:
  720.     // at least one digit and the terminating '\0'.
  721.     //
  722.     if (name[0] == U_0)
  723.     {
  724.         IntLiteralValue *int_literal = (IntLiteralValue *) (name[1] == U_x || name[1] == U_X
  725.                                                                      ? FindOrInsertHexInt(literal)
  726.                                                                      : FindOrInsertOctalInt(literal));
  727.         return FindOrInsert(- int_literal -> value);
  728.     }
  729.  
  730.     int value = 0;
  731.  
  732.     wchar_t *p;
  733.     for (p = name; *p; p++)
  734.     {
  735.         int digit = *p - U_0;
  736.         if (value > int32_limit || (value == int32_limit && digit > 8))
  737.             break;
  738.         value = value * 10 + digit;
  739.     }
  740.  
  741.     return (*p ? bad_value : FindOrInsert(-value));
  742. }
  743.  
  744.  
  745. void IntLiteralTable::Rehash()
  746. {
  747.     hash_size = primes[++prime_index];
  748.  
  749.     delete [] base;
  750.     base = (IntLiteralValue **) memset(new IntLiteralValue *[hash_size], 0, hash_size * sizeof(IntLiteralValue *));
  751.  
  752.     //
  753.     // Recall that the 0th element is unused.
  754.     //
  755.     for (int i = 1; i < symbol_pool.Length(); i++)
  756.     {
  757.         IntLiteralValue *ilv = symbol_pool[i];
  758.         int k = ((unsigned) ilv -> value) % hash_size; // The unsigned casting turns the negative values into positive values
  759.         ilv -> next = base[k];
  760.         base[k] = ilv;
  761.     }
  762.  
  763.     return;
  764. }
  765.  
  766.  
  767. IntLiteralValue *IntLiteralTable::Find(int value)
  768. {
  769.     int k = ((unsigned) value) % hash_size; // The unsigned casting turns the negative values into positive values
  770.  
  771.     IntLiteralValue *lit = NULL;
  772.     for (lit = base[k]; lit; lit = (IntLiteralValue *) lit -> next)
  773.     {
  774.         if (lit -> value == value)
  775.             break;
  776.     }
  777.  
  778.     return lit;
  779. }
  780.  
  781.  
  782. IntLiteralValue *IntLiteralTable::FindOrInsert(int value)
  783. {
  784.     int k = ((unsigned) value) % hash_size; // The unsigned casting turns the negative values into positive values
  785.  
  786.     IntLiteralValue *lit;
  787.     for (lit = base[k]; lit; lit = (IntLiteralValue *) lit -> next)
  788.     {
  789.         if (lit -> value == value)
  790.             return lit;
  791.     }
  792.  
  793.     lit = new IntLiteralValue();
  794.     lit -> Initialize(value, symbol_pool.Length());
  795.     symbol_pool.Next() = lit;
  796.  
  797.     lit -> next = base[k];
  798.     base[k] = lit;
  799.  
  800.     //
  801.     // If the number of unique elements in the hash table exceeds 2 times
  802.     // the size of the base, and we have not yet reached the maximum
  803.     // allowable size for a base, reallocate a larger base and rehash
  804.     // the elements.
  805.     //
  806.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  807.         Rehash();
  808.  
  809.     return lit;
  810. }
  811.  
  812.  
  813. LongInt LongLiteralTable::int64_limit = LongInt(0x7FFFFFFF, 0xFFFFFFFF) / 10;
  814. int LongLiteralTable::primes[] = {DEFAULT_HASH_SIZE, 2039, 4093, MAX_HASH_SIZE};
  815.  
  816. LongLiteralTable::LongLiteralTable(LiteralValue *bad_value_) : symbol_pool(16384),
  817.                                                                bad_value(bad_value_),
  818.                                                                prime_index(0),
  819.                                                                hash_size(primes[0])
  820. {
  821.     base = (LongLiteralValue **) memset(new LongLiteralValue *[hash_size], 0, hash_size * sizeof(LongLiteralValue *));
  822.     symbol_pool.Next() = NULL; // do not use the 0th element
  823. }
  824.  
  825. LongLiteralTable::~LongLiteralTable()
  826. {
  827. /*
  828. int n;
  829. int num_slots = 0;
  830. int total = 0;
  831. for (n = 0; n < hash_size; n++)
  832. {
  833. int num = 0;
  834. for (LiteralValue *s = base[n]; s; s = s -> next)
  835.     num++;
  836. if (num > 0)
  837. {
  838. num_slots++;
  839. total += num;
  840. }
  841. }
  842.  
  843. if (num_slots > 0)
  844. {
  845. Coutput << "\nDestroying the long table with " << total
  846.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  847. for (n = 0; n < hash_size; n++)
  848. {
  849. int num = 0;
  850. for (LiteralValue *s = base[n]; s; s = s -> next)
  851.     num++;
  852. if (num > 0)
  853. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  854. }
  855. }
  856. if (hash_size < total)
  857.     total = total;
  858. */
  859.  
  860. #ifdef TEST
  861.     for (int i = 0; i < symbol_pool.Length(); i++)
  862.         delete symbol_pool[i];
  863.     delete [] base;
  864. #endif
  865. }
  866.  
  867.  
  868. LiteralValue *LongLiteralTable::FindOrInsertHexLong(LiteralSymbol *literal)
  869. {
  870.     u4 high = 0,
  871.        low = 0;
  872.  
  873.     wchar_t *head = literal -> Name() + 1, // point to X
  874.             *tail = &literal -> Name()[literal -> NameLength() - 2]; // -2 to skip the 'L' suffix
  875.  
  876.     //
  877.     // According to the JLS 3.10.1, "A compile-time error occurs if ... a
  878.     // hexadecimal or octal int literal does not fit in 32 bits".
  879.     // So, strictly speaking, we should not skip leading zeroes. However,
  880.     // there are many publicly available code out there with leading zeroes
  881.     // that don't compile with jikes,...
  882.     //
  883.     {
  884.         for (++head; tail > head && *head == U_0; head++) // skip leading zeroes
  885.             ;
  886.         head--;
  887.     }
  888.  
  889.     for (int i = 0; i < 32 && tail > head; i += 4, tail--)
  890.     {
  891.         u4 d = *tail - (Code::IsDigit(*tail) ? U_0 : (Code::IsLower(*tail) ? U_a : U_A) - 10);
  892.         low |= (d << i);
  893.     }
  894.  
  895.     for (int j = 0; j < 32 && tail > head; j += 4, tail--)
  896.     {
  897.         u4 d = *tail - (Code::IsDigit(*tail) ? U_0 : (Code::IsLower(*tail) ? U_a : U_A) - 10);
  898.         high |= (d << j);
  899.     }
  900.  
  901.     return (tail > head ? bad_value : FindOrInsert(LongInt(high, low)));
  902. }
  903.  
  904.  
  905. LiteralValue *LongLiteralTable::FindOrInsertOctalLong(LiteralSymbol *literal)
  906. {
  907.     wchar_t *head = literal -> Name(), // point to initial '0'
  908.             *tail = &head[literal -> NameLength() - 2]; // -2 to skip the 'L' suffix
  909.  
  910.     ULongInt uvalue = 0;
  911.     //
  912.     // According to the JLS 3.10.1, "A compile-time error occurs if ... a
  913.     // hexadecimal or octal int literal does not fit in 32 bits".
  914.     // So, strictly speaking, we should not skip leading zeroes. However,
  915.     // there are many publicly available code out there with leading zeroes
  916.     // that don't compile with jikes,...
  917.     //
  918.     {
  919.         for (++head; tail > head && *head == U_0; head++) // skip leading zeroes
  920.             ;
  921.         head--;
  922.     }
  923.  
  924.     for (int i = 0; i < 63 && tail > head; i += 3, tail--)
  925.     {
  926.         ULongInt d = (u4) (*tail - U_0);
  927.         uvalue |= (d << i);
  928.     }
  929.  
  930.     if (tail > head)
  931.     {
  932.         u4 d = *tail - U_0;
  933.  
  934.         if (d <= 1) // max number that can fit in 1 bit
  935.         {
  936.             tail--;
  937.             uvalue.HighWord() |= (d << 31);
  938.         }
  939.     }
  940.  
  941.     return (tail > head ? bad_value : FindOrInsert((LongInt) uvalue));
  942. }
  943.  
  944.  
  945. LiteralValue *LongLiteralTable::FindOrInsertLong(LiteralSymbol *literal)
  946. {
  947.     wchar_t *name = literal -> Name();
  948.  
  949.     //
  950.     // We can assert that the name of a literal contains at least two characters:
  951.     // at least one digit and the terminating '\0'.
  952.     //
  953.     if (name[0] == U_0)
  954.         literal -> value = (name[1] == U_x || name[1] == U_X ? FindOrInsertHexLong(literal) : FindOrInsertOctalLong(literal));
  955.     else
  956.     {
  957.         LongInt value = 0;
  958.  
  959.         wchar_t *p;
  960.         for (p = name; *p != U_L && *p != U_l; p++)
  961.         {
  962.             u4 digit = *p - U_0;
  963.             if (value > int64_limit || (value == int64_limit && digit > 7))
  964.                 break;
  965.             value = value * 10 + digit;
  966.         }
  967.  
  968.         literal -> value = (*p != U_L && *p != U_l ? bad_value : FindOrInsert(value));
  969.     }
  970.  
  971.     return literal -> value;
  972. }
  973.  
  974.  
  975. LiteralValue *LongLiteralTable::FindOrInsertNegativeLong(LiteralSymbol *literal)
  976. {
  977.     if (literal -> value && literal -> value != bad_value) // a positive value already exists
  978.     {
  979.         LongLiteralValue *long_literal = (LongLiteralValue *) literal -> value;
  980.         return FindOrInsert(- long_literal -> value);
  981.     }
  982.  
  983.     wchar_t *name = literal -> Name();
  984.     //
  985.     // We can assert that the name of a literal contains at least two characters:
  986.     // at least one digit and the terminating '\0'.
  987.     //
  988.     if (name[0] == U_0)
  989.     {
  990.         LongLiteralValue *long_literal = (LongLiteralValue *) (name[1] == U_x || name[1] == U_X
  991.                                                                                ? FindOrInsertHexLong(literal)
  992.                                                                                : FindOrInsertOctalLong(literal));
  993.         return FindOrInsert(- long_literal -> value);
  994.     }
  995.  
  996.     LongInt value = 0;
  997.  
  998.     wchar_t *p;
  999.     for (p = name; *p != U_L && *p != U_l && value >= 0; p++)
  1000.     {
  1001.         u4 digit = *p - U_0;
  1002.         if (value > int64_limit || (value == int64_limit && digit > 8))
  1003.             break;
  1004.         value = value * 10 + digit;
  1005.     }
  1006.  
  1007.     return (*p != U_L && *p != U_l ? bad_value : FindOrInsert(-value));
  1008. }
  1009.  
  1010.  
  1011. void LongLiteralTable::Rehash()
  1012. {
  1013.     hash_size = primes[++prime_index];
  1014.  
  1015.     delete [] base;
  1016.     base = (LongLiteralValue **) memset(new LongLiteralValue *[hash_size], 0, hash_size * sizeof(LongLiteralValue *));
  1017.  
  1018.     //
  1019.     // Recall that the 0th element is unused.
  1020.     //
  1021.     for (int i = 1; i < symbol_pool.Length(); i++)
  1022.     {
  1023.         LongLiteralValue *llv = symbol_pool[i];
  1024.         int k = (((ULongInt) llv -> value) % ULongInt(0, hash_size)).LowWord(); // The ULongInt turns negative values positive
  1025.         llv -> next = base[k];
  1026.         base[k] = llv;
  1027.     }
  1028.  
  1029.     return;
  1030. }
  1031.  
  1032.  
  1033. LongLiteralValue *LongLiteralTable::FindOrInsert(LongInt value)
  1034. {
  1035.     int k = (((ULongInt) value) % ULongInt(0, hash_size)).LowWord();  // The ULongInt cast turns negative values into positive values
  1036.  
  1037.     LongLiteralValue *lit;
  1038.     for (lit = base[k]; lit; lit = (LongLiteralValue *) lit -> next)
  1039.     {
  1040.         if (lit -> value == value)
  1041.             return lit;
  1042.     }
  1043.  
  1044.     lit = new LongLiteralValue();
  1045.     lit -> Initialize(value, symbol_pool.Length());
  1046.     symbol_pool.Next() = lit;
  1047.  
  1048.     lit -> next = base[k];
  1049.     base[k] = lit;
  1050.  
  1051.     //
  1052.     // If the number of unique elements in the hash table exceeds 2 times
  1053.     // the size of the base, and we have not yet reached the maximum
  1054.     // allowable size for a base, reallocate a larger base and rehash
  1055.     // the elements.
  1056.     //
  1057.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  1058.         Rehash();
  1059.  
  1060.     return lit;
  1061. }
  1062.  
  1063.  
  1064. int FloatLiteralTable::primes[] = {DEFAULT_HASH_SIZE, 2039, 4093, MAX_HASH_SIZE};
  1065.  
  1066. FloatLiteralTable::FloatLiteralTable(LiteralValue *bad_value_) : symbol_pool(16384),
  1067.                                                                  bad_value(bad_value_),
  1068.                                                                  prime_index(0),
  1069.                                                                  hash_size(primes[0])
  1070. {
  1071.     base = (FloatLiteralValue **) memset(new FloatLiteralValue *[hash_size], 0, hash_size * sizeof(FloatLiteralValue *));
  1072.     symbol_pool.Next() = NULL; // do not use the 0th element
  1073. }
  1074.  
  1075. FloatLiteralTable::~FloatLiteralTable()
  1076. {
  1077. /*
  1078. int n;
  1079. int num_slots = 0;
  1080. int total = 0;
  1081. for (n = 0; n < hash_size; n++)
  1082. {
  1083. int num = 0;
  1084. for (LiteralValue *s = base[n]; s; s = s -> next)
  1085.     num++;
  1086. if (num > 0)
  1087. {
  1088. num_slots++;
  1089. total += num;
  1090. }
  1091. }
  1092.  
  1093. if (num_slots > 0)
  1094. {
  1095. Coutput << "\nDestroying the float table with " << total
  1096.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  1097. for (n = 0; n < hash_size; n++)
  1098. {
  1099. int num = 0;
  1100. for (LiteralValue *s = base[n]; s; s = s -> next)
  1101.     num++;
  1102. if (num > 0)
  1103. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  1104. }
  1105. }
  1106. if (hash_size < total)
  1107.     total = total;
  1108. */
  1109.  
  1110. #ifdef TEST
  1111.     for (int i = 0; i < symbol_pool.Length(); i++)
  1112.         delete symbol_pool[i];
  1113.     delete [] base;
  1114. #endif
  1115. }
  1116.  
  1117.  
  1118. LiteralValue *FloatLiteralTable::FindOrInsertFloat(LiteralSymbol *literal)
  1119. {
  1120.     char *name = new char[literal -> NameLength() + 1];
  1121.     for (int i = 0; i < literal -> NameLength(); i++)
  1122.         name[i] = (char) literal -> Name()[i];
  1123.     name[literal -> NameLength()] = U_NULL;
  1124.  
  1125.     IEEEfloat value = IEEEfloat(name);
  1126.  
  1127.     literal -> value = FindOrInsert(value);
  1128.  
  1129.     delete [] name;
  1130.  
  1131.     return literal -> value;
  1132. }
  1133.  
  1134.  
  1135. void FloatLiteralTable::Rehash()
  1136. {
  1137.     hash_size = primes[++prime_index];
  1138.  
  1139.     delete [] base;
  1140.     base = (FloatLiteralValue **) memset(new FloatLiteralValue *[hash_size], 0, hash_size * sizeof(FloatLiteralValue *));
  1141.  
  1142.     //
  1143.     // Recall that the 0th element is unused.
  1144.     //
  1145.     for (int i = 1; i < symbol_pool.Length(); i++)
  1146.     {
  1147.         FloatLiteralValue *flv = symbol_pool[i];
  1148.         int k = Hash(flv -> value) % hash_size; // the hash function for float values is cheap so we don't need to save it.
  1149.         flv -> next = base[k];
  1150.         base[k] = flv;
  1151.     }
  1152.  
  1153.     return;
  1154. }
  1155.  
  1156.  
  1157. FloatLiteralValue *FloatLiteralTable::FindOrInsert(IEEEfloat value)
  1158. {
  1159.     int k = Hash(value) % hash_size;
  1160.  
  1161.     FloatLiteralValue *lit;
  1162.     for (lit = base[k]; lit; lit = (FloatLiteralValue *) lit -> next)
  1163.     {
  1164.         if (lit -> value == value)
  1165.             return lit;
  1166.     }
  1167.  
  1168.     lit = new FloatLiteralValue();
  1169.     lit -> Initialize(value, symbol_pool.Length());
  1170.     symbol_pool.Next() = lit;
  1171.  
  1172.     lit -> next = base[k];
  1173.     base[k] = lit;
  1174.  
  1175.     //
  1176.     // If the number of unique elements in the hash table exceeds 2 times
  1177.     // the size of the base, and we have not yet reached the maximum
  1178.     // allowable size for a base, reallocate a larger base and rehash
  1179.     // the elements.
  1180.     //
  1181.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  1182.         Rehash();
  1183.  
  1184.     return lit;
  1185. }
  1186.  
  1187.  
  1188. int DoubleLiteralTable::primes[] = {DEFAULT_HASH_SIZE, 2039, 4093, MAX_HASH_SIZE};
  1189.  
  1190. DoubleLiteralTable::DoubleLiteralTable(LiteralValue *bad_value_) : symbol_pool(16384),
  1191.                                                                    bad_value(bad_value_),
  1192.                                                                    prime_index(0),
  1193.                                                                    hash_size(primes[0])
  1194. {
  1195.     base = (DoubleLiteralValue **) memset(new DoubleLiteralValue *[hash_size], 0, hash_size * sizeof(DoubleLiteralValue *));
  1196.     symbol_pool.Next() = NULL; // do not use the 0th element
  1197. }
  1198.  
  1199. DoubleLiteralTable::~DoubleLiteralTable()
  1200. {
  1201. /*
  1202. int n;
  1203. int num_slots = 0;
  1204. int total = 0;
  1205. for (n = 0; n < hash_size; n++)
  1206. {
  1207. int num = 0;
  1208. for (LiteralValue *s = base[n]; s; s = s -> next)
  1209.     num++;
  1210. if (num > 0)
  1211. {
  1212. num_slots++;
  1213. total += num;
  1214. }
  1215. }
  1216.  
  1217. if (num_slots > 0)
  1218. {
  1219. Coutput << "\nDestroying the double table with " << total
  1220.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  1221. for (n = 0; n < hash_size; n++)
  1222. {
  1223. int num = 0;
  1224. for (LiteralValue *s = base[n]; s; s = s -> next)
  1225.     num++;
  1226. if (num > 0)
  1227. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  1228. }
  1229. }
  1230. if (hash_size < total)
  1231.     total = total;
  1232. */
  1233. #ifdef TEST
  1234.     for (int i = 0; i < symbol_pool.Length(); i++)
  1235.         delete symbol_pool[i];
  1236.     delete [] base;
  1237. #endif
  1238. }
  1239.  
  1240.  
  1241. LiteralValue *DoubleLiteralTable::FindOrInsertDouble(LiteralSymbol *literal)
  1242. {
  1243.     char *name = new char[literal -> NameLength() + 1];
  1244.     for (int i = 0; i < literal -> NameLength(); i++)
  1245.         name[i] = (char) literal -> Name()[i];
  1246.     name[literal -> NameLength()] = U_NULL;
  1247.  
  1248.     IEEEdouble value = IEEEdouble(name);
  1249.  
  1250.     literal -> value = FindOrInsert(value);
  1251.  
  1252.     delete [] name;
  1253.  
  1254.     return literal -> value;
  1255. }
  1256.  
  1257.  
  1258. void DoubleLiteralTable::Rehash()
  1259. {
  1260.     hash_size = primes[++prime_index];
  1261.  
  1262.     delete [] base;
  1263.     base = (DoubleLiteralValue **) memset(new DoubleLiteralValue *[hash_size], 0, hash_size * sizeof(DoubleLiteralValue *));
  1264.  
  1265.     //
  1266.     // Recall that the 0th element is unused.
  1267.     //
  1268.     for (int i = 1; i < symbol_pool.Length(); i++)
  1269.     {
  1270.         DoubleLiteralValue *dlv = symbol_pool[i];
  1271.         int k = Hash(dlv -> value) % hash_size; // the hash function for double values is cheap so we don't need to save it.
  1272.         dlv -> next = base[k];
  1273.         base[k] = dlv;
  1274.     }
  1275.  
  1276.     return;
  1277. }
  1278.  
  1279.  
  1280. DoubleLiteralValue *DoubleLiteralTable::FindOrInsert(IEEEdouble value)
  1281. {
  1282.     int k = Hash(value) % hash_size;
  1283.  
  1284.     DoubleLiteralValue *lit;
  1285.     for (lit = base[k]; lit; lit = (DoubleLiteralValue *) lit -> next)
  1286.     {
  1287.         if (lit -> value == value)
  1288.             return lit;
  1289.     }
  1290.  
  1291.     lit = new DoubleLiteralValue();
  1292.     lit -> Initialize(value, symbol_pool.Length());
  1293.     symbol_pool.Next() = lit;
  1294.  
  1295.     lit -> next = base[k];
  1296.     base[k] = lit;
  1297.  
  1298.     //
  1299.     // If the number of unique elements in the hash table exceeds 2 times
  1300.     // the size of the base, and we have not yet reached the maximum
  1301.     // allowable size for a base, reallocate a larger base and rehash
  1302.     // the elements.
  1303.     //
  1304.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  1305.         Rehash();
  1306.  
  1307.     return lit;
  1308. }
  1309.  
  1310.  
  1311. LiteralValue *Utf8LiteralTable::FindOrInsertString(LiteralSymbol *literal)
  1312. {
  1313.     wchar_t *name = literal -> Name();
  1314.  
  1315.     int literal_length = literal -> NameLength();
  1316.  
  1317.     char *value = new char[literal_length * 3]; // should be big enough for the worst case
  1318.     int len = 0,
  1319.         i;
  1320.     for (i = 1; i < literal_length && name[i] != U_DOUBLE_QUOTE; i++)  // start at 1 to skip the initial \"
  1321.     {
  1322.         int ch = name[i];
  1323.  
  1324.         if (ch == U_BACKSLASH)
  1325.         {
  1326.             if (name[i + 1] == U_b)
  1327.             {
  1328.                 i++;
  1329.                 ch = U_BACKSPACE;
  1330.             }
  1331.             else if (name[i + 1] == U_t)
  1332.             {
  1333.                 i++;
  1334.                 ch = U_HORIZONTAL_TAB;
  1335.             }
  1336.             else if (name[i + 1] == U_n)
  1337.             {
  1338.                 i++;
  1339.                 ch = U_LINE_FEED;
  1340.             }
  1341.             else if (name[i + 1] == U_f)
  1342.             {
  1343.                 i++;
  1344.                 ch = U_FORM_FEED;
  1345.             }
  1346.             else if (name[i + 1] == U_r)
  1347.             {
  1348.                 i++;
  1349.                 ch = U_CARRIAGE_RETURN;
  1350.             }
  1351.             else if (name[i + 1] == U_DOUBLE_QUOTE)
  1352.             {
  1353.                 i++;
  1354.                 ch = U_DOUBLE_QUOTE;
  1355.             }
  1356.             else if (name[i + 1] == U_SINGLE_QUOTE)
  1357.             {
  1358.                 i++;
  1359.                 ch = U_SINGLE_QUOTE;
  1360.             }
  1361.             else if (name[i + 1] == U_BACKSLASH)
  1362.             {
  1363.                 i++;
  1364.                 ch = U_BACKSLASH;
  1365.             }
  1366.             else if (Code::IsDigit(name[i + 1]))
  1367.             {
  1368.                 int digit = name[++i] - U_0;
  1369.  
  1370.                 if (digit > 7) // The first digit must be an octal digit
  1371.                     ch = -1;
  1372.                 else
  1373.                 {
  1374.                     ch = digit;
  1375.                     if (Code::IsDigit(name[i + 1]))
  1376.                     {
  1377.                         digit = name[i + 1] - U_0;
  1378.                         if (digit < 8)
  1379.                         {
  1380.                             ch = ch * 8 + digit;
  1381.                             i++;
  1382.                             if (Code::IsDigit(name[i + 1]))
  1383.                             {
  1384.                                 digit = name[i + 1] - U_0;
  1385.                                 if (ch <= 0x1F && digit < 8)
  1386.                                 {
  1387.                                     ch = ch * 8 + digit;
  1388.                                     i++;
  1389.                                 }
  1390.                             }
  1391.                         }
  1392.                     }
  1393.                 }
  1394.             }
  1395.             else ch = -1;
  1396.         }
  1397.  
  1398.         if (ch < 0)
  1399.              break;
  1400.         else if (ch == 0)
  1401.         {
  1402.              value[len++] = (char) 0xC0;
  1403.              value[len++] = (char) 0x80;
  1404.         }
  1405.         else if (ch <= 0x007F)
  1406.              value[len++] = (char) ch;
  1407.         else if (ch <= 0x07FF)
  1408.         {
  1409.              value[len++] = (char) ((char) 0xC0 | (char) ((ch >> 6) & 0x001F)); // bits 6-10
  1410.              value[len++] = (char) ((char) 0x80 | (char) (ch & 0x003F));        // bits 0-5
  1411.         }
  1412.         else
  1413.         {
  1414.              value[len++] = (char) ((char) 0xE0 | (char) ((ch >> 12) & 0x000F));
  1415.              value[len++] = (char) ((char) 0x80 | (char) ((ch >> 6) & 0x003F));
  1416.              value[len++] = (char) ((char) 0x80 | (char) (ch & 0x3F));
  1417.         }
  1418.     }
  1419.  
  1420.     value[len] = U_NULL;
  1421.     literal -> value = (i < literal_length && name[i] != U_DOUBLE_QUOTE ? bad_value : FindOrInsert(value, len));
  1422.  
  1423.     delete [] value;
  1424.     return literal -> value;
  1425. }
  1426.  
  1427.  
  1428. Utf8LiteralValue *Utf8LiteralTable::FindOrInsert(wchar_t ch)
  1429. {
  1430.     int len = 0;
  1431.     char str[4];
  1432.  
  1433.     if (ch == 0)
  1434.     {
  1435.          str[len++] = (char) 0xC0;
  1436.          str[len++] = (char) 0x80;
  1437.     }
  1438.     else if (ch <= 0x007F)
  1439.          str[len++] = (char) ch;
  1440.     else if (ch <= 0x07FF)
  1441.     {
  1442.          str[len++] = (char) ((char) 0xC0 | (char) ((ch >> 6) & 0x001F)); // bits 6-10
  1443.          str[len++] = (char) ((char) 0x80 | (char) (ch & 0x003F));        // bits 0-5
  1444.     }
  1445.     else
  1446.     {
  1447.          str[len++] = (char) ((char) 0xE0 | (char) ((ch >> 12) & 0x000F));
  1448.          str[len++] = (char) ((char) 0x80 | (char) ((ch >> 6) & 0x003F));
  1449.          str[len++] = (char) ((char) 0x80 | (char) (ch & 0x3F));
  1450.     }
  1451.  
  1452.     str[len] = U_NULL;
  1453.  
  1454.     return FindOrInsert(str, len);
  1455. }
  1456.  
  1457.  
  1458. void Utf8LiteralTable::Rehash()
  1459. {
  1460.     hash_size = primes[++prime_index];
  1461.  
  1462.     delete [] base;
  1463.     base = (Utf8LiteralValue **) memset(new Utf8LiteralValue *[hash_size], 0, hash_size * sizeof(Utf8LiteralValue *));
  1464.  
  1465.     //
  1466.     // Recall that the 0th element is unused.
  1467.     //
  1468.     for (int i = 1; i < symbol_pool.Length(); i++)
  1469.     {
  1470.         Utf8LiteralValue *ulv = symbol_pool[i];
  1471.         int k = ulv -> hash_address % hash_size;
  1472.         ulv -> next = base[k];
  1473.         base[k] = ulv;
  1474.     }
  1475.  
  1476.     return;
  1477. }
  1478.  
  1479.  
  1480. int Utf8LiteralTable::primes[] = {DEFAULT_HASH_SIZE, 8191, 16411, MAX_HASH_SIZE};
  1481.  
  1482. Utf8LiteralTable::Utf8LiteralTable(LiteralValue *bad_value_) : symbol_pool(16384),
  1483.                                                                bad_value(bad_value_),
  1484.                                                                prime_index(0),
  1485.                                                                hash_size(primes[0])
  1486. {
  1487.     base = (Utf8LiteralValue **) memset(new Utf8LiteralValue *[hash_size], 0, hash_size * sizeof(Utf8LiteralValue *));
  1488.     symbol_pool.Next() = NULL; // do not use the 0th element
  1489. }
  1490.  
  1491.  
  1492. Utf8LiteralTable::~Utf8LiteralTable()
  1493. {
  1494. /*
  1495. int n;
  1496. int num_slots = 0;
  1497. int total = 0;
  1498. for (n = 0; n < hash_size; n++)
  1499. {
  1500. int num = 0;
  1501. for (LiteralValue *s = base[n]; s; s = s -> next)
  1502.     num++;
  1503. if (num > 0)
  1504. {
  1505. num_slots++;
  1506. total += num;
  1507. }
  1508. }
  1509.  
  1510. if (num_slots > 0)
  1511. {
  1512. Coutput << "\nDestroying the Utf8 table with " << total
  1513.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  1514. for (n = 0; n < hash_size; n++)
  1515. {
  1516. int num = 0;
  1517. for (LiteralValue *s = base[n]; s; s = s -> next)
  1518.     num++;
  1519. if (num > 0)
  1520. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  1521. }
  1522. }
  1523. if (hash_size < total)
  1524.     total = total;
  1525. */
  1526. #ifdef TEST
  1527.     for (int i = 0; i < symbol_pool.Length(); i++)
  1528.         delete symbol_pool[i];
  1529.     delete [] base;
  1530. #endif
  1531. }
  1532.  
  1533.  
  1534. Utf8LiteralValue *Utf8LiteralTable::FindOrInsert(char *str, int len)
  1535. {
  1536.     unsigned hash_address = Hash(str, len);
  1537.     int k = hash_address % hash_size;
  1538.  
  1539.     Utf8LiteralValue *lit;
  1540.     for (lit = base[k]; lit; lit = (Utf8LiteralValue *) lit -> next)
  1541.     {
  1542.         if (len == lit -> length)
  1543.         {
  1544.             if (memcmp(lit -> value, str, len * sizeof(char)) == 0)
  1545.                  return lit;
  1546.         }
  1547.     }
  1548.  
  1549.     lit = new Utf8LiteralValue();
  1550.     lit -> Initialize(str, len, hash_address, symbol_pool.Length());
  1551.     symbol_pool.Next() = lit;
  1552.  
  1553.     lit -> next = base[k];
  1554.     base[k] = lit;
  1555.  
  1556.     //
  1557.     // If the number of unique elements in the hash table exceeds 2 times
  1558.     // the size of the base, and we have not yet reached the maximum
  1559.     // allowable size for a base, reallocate a larger base and rehash
  1560.     // the elements.
  1561.     //
  1562.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  1563.         Rehash();
  1564.  
  1565.     return lit;
  1566. }
  1567.  
  1568.  
  1569. bool Utf8LiteralTable::IsConstant(AstExpression *expression)
  1570. {
  1571.     //
  1572.     // Recall that addition if left-recursive
  1573.     //
  1574.     while (! expression -> IsConstant())
  1575.     {
  1576.         AstBinaryExpression *binary_expression;
  1577.         AstCastExpression *cast_expression;
  1578.         AstParenthesizedExpression *parenthesized_expression;
  1579.  
  1580.         if (binary_expression = expression -> BinaryExpressionCast())
  1581.         {
  1582.              AstExpression *right = binary_expression -> right_expression;
  1583.              if (! IsConstant(right))
  1584.                  return false;
  1585.              expression = binary_expression -> left_expression;
  1586.         }
  1587.         else if (cast_expression = expression -> CastExpressionCast())
  1588.              expression = cast_expression -> expression;
  1589.         else if (parenthesized_expression = expression -> ParenthesizedExpressionCast())
  1590.              expression = parenthesized_expression -> expression;
  1591.         else return false; // Not a constant String expression
  1592.     }
  1593.  
  1594.     if (expression -> IsConstant())
  1595.         expr -> Next() = expression;
  1596.  
  1597.     return expression -> IsConstant();
  1598. }
  1599.  
  1600.  
  1601. void Utf8LiteralTable::CheckStringConstant(AstExpression *expression)
  1602. {
  1603.     expr = new Tuple<AstExpression *>(256);
  1604.  
  1605.     if (IsConstant(expression))
  1606.     {
  1607.         Utf8LiteralValue *literal;
  1608.         int length = 0;
  1609.         for (int i = 0; i < expr -> Length(); i++)
  1610.         {
  1611.             literal = (Utf8LiteralValue *) (*expr)[i] -> value;
  1612.             length += literal -> length;
  1613.         }
  1614.         char *str = new char[length + 1]; // +1 for '\0'
  1615.  
  1616.         //
  1617.         // Since we started on the right, we have to run over the list in reverse order.
  1618.         //
  1619.         int index = 0;
  1620.         for (int k = expr -> Length() - 1; k >= 0; k--)
  1621.         {
  1622.             literal = (Utf8LiteralValue *) (*expr)[k] -> value;
  1623.  
  1624.             assert(literal -> value);
  1625.  
  1626.             memmove(&str[index], literal -> value, literal -> length * sizeof(char));
  1627.             index += literal -> length;
  1628.         }
  1629.         str[length] = U_NULL;
  1630.  
  1631.         expression -> value = FindOrInsert(str, length);
  1632.  
  1633.         delete [] str;
  1634.     }
  1635.  
  1636.     delete expr;
  1637.  
  1638.     return;
  1639. }
  1640.  
  1641.  
  1642. int LiteralLookupTable::primes[] = {DEFAULT_HASH_SIZE, 2039, 4093, MAX_HASH_SIZE};
  1643.  
  1644. LiteralLookupTable::LiteralLookupTable() : symbol_pool(16384),
  1645.                                            prime_index(0),
  1646.                                            hash_size(primes[0])
  1647. {
  1648.     base = (LiteralSymbol **) memset(new LiteralSymbol *[hash_size], 0, hash_size * sizeof(LiteralSymbol *));
  1649. }
  1650.  
  1651. LiteralLookupTable::~LiteralLookupTable()
  1652. {
  1653. /*
  1654. int n;
  1655. int num_slots = 0;
  1656. int total = 0;
  1657. for (n = 0; n < hash_size; n++)
  1658. {
  1659. int num = 0;
  1660. for (Symbol *s = base[n]; s; s = s -> next)
  1661.     num++;
  1662. if (num > 0)
  1663. {
  1664. num_slots++;
  1665. total += num;
  1666. }
  1667. }
  1668.  
  1669. if (num_slots > 0)
  1670. {
  1671. Coutput << "\nDestroying the Literal table with " << total
  1672.         << " elements and base size " << hash_size << " containing " << num_slots << " non-empty slots\n";
  1673. for (n = 0; n < hash_size; n++)
  1674. {
  1675. int num = 0;
  1676. for (Symbol *s = base[n]; s; s = s -> next)
  1677.     num++;
  1678. if (num > 0)
  1679. Coutput << "    slot " << n << " contains " << num << " element(s)\n";
  1680. }
  1681. }
  1682. if (hash_size < total)
  1683.     total = total;
  1684. */
  1685. #ifdef TEST
  1686.     for (int i = 0; i < symbol_pool.Length(); i++)
  1687.         delete symbol_pool[i];
  1688.     delete [] base;
  1689. #endif
  1690. }
  1691.  
  1692.  
  1693. void LiteralLookupTable::Rehash()
  1694. {
  1695.     hash_size = primes[++prime_index];
  1696.  
  1697.     delete [] base;
  1698.     base = (LiteralSymbol **) memset(new LiteralSymbol *[hash_size], 0, hash_size * sizeof(LiteralSymbol *));
  1699.  
  1700.     for (int i = 0; i < symbol_pool.Length(); i++)
  1701.     {
  1702.         LiteralSymbol *ls = symbol_pool[i];
  1703.         int k = ls -> hash_address % hash_size;
  1704.         ls -> next = base[k];
  1705.         base[k] = ls;
  1706.     }
  1707.  
  1708.     return;
  1709. }
  1710.  
  1711.  
  1712. LiteralSymbol *LiteralLookupTable::FindOrInsertLiteral(wchar_t *str, int len)
  1713. {
  1714.     unsigned hash_address = Hash(str, len);
  1715.     int k = hash_address % hash_size;
  1716.     LiteralSymbol *symbol;
  1717.     for (symbol = base[k]; symbol; symbol = (LiteralSymbol *) symbol -> next)
  1718.     {
  1719.         if (len == symbol -> NameLength() && memcmp(symbol -> Name(), str, len * sizeof(wchar_t)) == 0)
  1720.             return symbol;
  1721.     }
  1722.  
  1723.     symbol = new LiteralSymbol();
  1724.     symbol_pool.Next() = symbol;
  1725.     symbol -> Initialize(str, hash_address, len);
  1726.  
  1727.     symbol -> next = base[k];
  1728.     base[k] = symbol;
  1729.  
  1730.     //
  1731.     // If the number of unique elements in the hash table exceeds 2 times
  1732.     // the size of the base, and we have not yet reached the maximum
  1733.     // allowable size for a base, reallocate a larger base and rehash
  1734.     // the elements.
  1735.     //
  1736.     if ((symbol_pool.Length() > (hash_size << 1)) && (hash_size < MAX_HASH_SIZE))
  1737.         Rehash();
  1738.  
  1739.     return symbol;
  1740. }
  1741.